package main

func main() {

	//root = [4,2,9,3,5,null,7]
	node3 := TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node5 := TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node1 := TreeNode{
		Val:   2,
		Left:  &node3,
		Right: &node4,
	}
	node2 := TreeNode{
		Val:   9,
		Left:  nil,
		Right: &node5,
	}
	root := TreeNode{
		Val:   4,
		Left:  &node1,
		Right: &node2,
	}

	//打印测试用例返回结果
	resp := levelOrder(&root)
	for _, v := range resp {
		for _, r := range v {
			print(r)
		}
		println("")
	}

}

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/* Everyday by my self im breaking down
I dont wanna fight alone anymore
bring me out
from prison in my own pride ,  */

//建立一个 二元组 记录层序和val
type TempMap struct {
	level int       //层序
	value *TreeNode //二叉树结点
}

//使用队列进行层序遍历
func levelOrder(root *TreeNode) [][]int {
	Queue := []TempMap{}   //队列(该队列类型是key-value pair)
	ans := [][]int{}       //结果数组
	tempArr := []TempMap{} //暂存数组

	if root == nil { //边界条件
		return nil
	}
	rootTempMap := TempMap{
		level: 0,
		value: root,
	}
	Queue = append(Queue, rootTempMap) //入队
	//只要队列不为空就一直死循环
	for len(Queue) != 0 {

		//队列首元素的value的左右儿子、队列首元素的level
		left, right, level := Queue[0].value.Left, Queue[0].value.Right, Queue[0].level
		if left != nil {
			rootTempMap.level = level + 1
			rootTempMap.value = left
			Queue = append(Queue, rootTempMap) //入队
			//enqueue tempMap.level++,value
		}
		if right != nil {
			rootTempMap.level = level + 1
			rootTempMap.value = right
			Queue = append(Queue, rootTempMap) //入队
			//enqueue tempMap.level++,value
		}
		//暂时存进temp数组
		tempArr = append(tempArr, Queue[0])
		//dequeue
		Queue = Queue[1:]
	}
	//-------------------开始根据temp数组的值level，分批存进ans数组
	tempArrLen := len(tempArr)
	for i := 0; i <= tempArr[tempArrLen-1].level; i++ { //取最后的层数为循环次数
		ans = append(ans, []int{}) //追加一个空数组
	}
	currentLevel := -1
	for i := 0; i < tempArrLen; i++ {
		currentLevel = tempArr[i].level
		ans[currentLevel] = append(ans[currentLevel], tempArr[i].value.Val)
	}
	//-------------------结束根据temp数组的值level，分批存进ans数组
	return ans

}
